//package mip;
//
//import java.io.PrintStream;
//import java.util.Scanner;
//
///*
// *  5.3. Dijkstra Algorithm
//
//Taken from: http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html
//
//Dijkstra's algorithm (invented by Edsger W. Dijkstra) solves the problem of finding the shortest path from a point in a graph (the source) to a destination. It turns out that one can find the shortest paths from a given source to all points in a graph in the same time, hence this problem is called the Single-source shortest paths problem.
//
//This problem is related to the spanning tree. The graph representing all the paths from one vertex to all the others must be a spanning tree - it must include all vertices. There will also be no cycles as a cycle would define more than one path from the selected vertex to at least one other vertex. For a graph, G=(V,E) where V is a set of vertices and E is a set of edges.
//
//Dijkstra's algorithm keeps two sets of vertices: S (the set of vertices whose shortest paths from the source have already been determined) and V-S (the remaining vertices). The other data structures needed are: d (array of best estimates of shortest path to each vertex) & pi (an array of predecessors for each vertex)
//
//The basic mode of operation is:
//
//   1.
//
//      Initialise d and pi,
//   2.
//
//      Set S to empty,
//   3.
//
//      While there are still vertices in V-S,
//         1.
//
//            Sort the vertices in V-S according to the current best estimate of their distance from source,
//         2.
//
//            Add u, the closest vertex in V-S, to S,
//         3.
//
//            Relax all the vertices still in V-S connected to u
//
//Dijkstra Algorithm:
//
//DIJKSTRA(Graph G,Node s)
//  initialize_single_source(G,s)
//  S:={ 0 }       /* Make S empty */
//  Q:=Vertices(G) /* Put the vertices in a PQ */
//  while not Empty(Q)
//    u:=ExtractMin(Q);
//    AddNode(S,u); /* Add u to S */
//    for each vertex v which is Adjacent with u
//      relax(u,v,w)
// */
//
//
///**
// * to solve the UVA MPI Maelstrom 423 problem
// * @author Jonas Jeske www.inf.ufrgs.br/~jjeske
// * 
// * using Dikjstras algorithm
// * status: not verified yet
// *
// */
//public class Main {
//	
//	
//	
//	public static void main(String[] args){
//		Main mpi = new Main();
//		mpi.begin();
//	}
//
//	private void begin() {
//		Scanner entrada = new Scanner(System.in);
//		PrintStream saida = new PrintStream(System.out);
//		
//		
//	}
//	
//	
//}
//	